package ljl.alg.wangzheng_camp.round1.sort;

/**
 * 刚看的左神的书上写的
 * 分成三个区域，两个指针，一个 left，一个 right
 * 0 1 2
 *
 * 这个题很巧妙的，没那么简单，不是反转链表那种题
 *
 * 左神的解法我忘了，我决定直接看答案了
 *
 * */
public class _75_sort_color {
    
    /**
     * 单指针
     * */
    public void sortColors1(int[] nums) {
        int ptr = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                swap(nums, ptr++, i);
            }
        }
        for (int i = ptr; i < nums.length; i++) {
            if (nums[i] == 1) {
                swap(nums, ptr++, i);
            }
        }
    }
    void swap(int[] nums, int l, int r) {
        if (l != r) {
            int t = nums[l]; nums[l] = nums[r]; nums[r] = t;
        }
    }
    
    /**
     * 看了答案提示还是做不出来，真是憋屈啊！
     *
     * 双指针 p0 p1
     * 210 - 120 - 021,012 -
     * 120
     * */
    public void sortColors2(int[] nums) {
        // 这两个是 0 和 1 下一个位置
        int p0 = 0, p1 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1)
                swap(nums, i, p1++);
            else if (nums[i] == 0) {
                swap(nums, i, p0);
                if (p0 < p1) {
                    swap(nums, i, p1);
                }
                p0++;
                p1++;
            }
        }
    }
    
    /**
     * 独特解法
     *
     * 1. 碰到 0 和 p0 交换，换出来的是 0 怎么办？
     * 2. 碰到 2 和 p2 交换，换出来的是 2 怎么办？
     * 010201
     * 0022
     *
     * 不知道为什么是这样的，兄弟萌，我吐了
     *
     * */
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; ++i) {
            while (i < p2 && nums[i] == 2) {
                swap(nums, i, p2--);
            }
            if (nums[i] == 0) {
                swap(nums, i, p0++);
            }
        }
    }
    
}
